/**
 * 由于本工程为C语言开发环境，此代码使用cpp语法，故仅做汇总。
 * 运行调试使用Cpp_training工程。
 */

#include <stdio.h>
#include <stdlib.h>

// 二叉树结点类型
typedef char ElemType_Tree;
// 二叉树结点
typedef struct BiTNode {
    ElemType_Tree data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

// 链表结点类型
typedef BiTNode* ElemType_Queue;
// 链表结点
typedef struct LinkQNode {
    ElemType_Queue data;
    struct LinkQNode *next;
}LinkQNode, *LinkList;
// 队列
typedef struct LinkQueue {
    LinkQNode *front, *rear;
}LinkQueue;




/**
 * 队列操作：初始化（不带头结点）
 * @return 队列数据类型
 */

LinkQueue InitQueue() {
    LinkQueue Q;
    Q.front = NULL;
    Q.rear = NULL;
    return Q;
}

/**
 * 队列操作：判空
 * @param Q
 * @return  队列为空返回true，队列非空返回false
 */
bool IsQueueEmpty(LinkQueue Q) {
    if (Q.front == Q.rear && Q.front == NULL) {
        return true;
    }
    return false;
}

/**
 * 队列操作：入队
 * @param Q
 * @param e
 */
void EnQueue(LinkQueue &Q, ElemType_Queue e) {
    LinkQNode *qNew = (LinkQNode*) calloc(1, sizeof (LinkQNode));
    qNew -> data = e;
    // 队列判空
    if (IsQueueEmpty(Q)) {
        Q.front = qNew;
        Q.rear = qNew;
        return;
    }
    // 队列非空
    qNew->next = Q.rear->next;
    Q.rear->next = qNew;
    Q.rear = Q.rear->next;
}

/**
 * 队列操作：出队
 * @param Q 队列
 * @param e 出队的元素通过变量e返回
 * @return  出队成功返回true，出队失败返回false
 */
bool DeQueue(LinkQueue &Q, ElemType_Queue &e) {
    // 队列判空
    if (IsQueueEmpty(Q)) {
        return false;
    }
    // 判断队列是否只剩一个元素
    e = Q.front->data;
    if (Q.front == Q.rear) {
        Q.front = NULL;
        Q.rear = NULL;
        return true;
    }
    LinkQNode *tmp = Q.front;
    Q.front = tmp->next;
    free(tmp);
    return true;
}

/**
 * 队列操作：遍历打印队列当前元素
 * @param Q
 */
void PrintQueue(LinkQueue Q) {
    // 队列判空
    if (IsQueueEmpty(Q)) {
        printf("NULL\n");
        return;
    }

    LinkQNode *pcur = Q.front;  // 记录当前指针位置
    while (pcur != NULL) {
        printf("%c", pcur->data->data);
        pcur = pcur->next;
    }
    printf("\n");
}

/**
 * 中序遍历二叉树
 * @param T
 */
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        printf("%c", T->data);
        InOrder(T->rchild);
    }
}

/**
 * 后序遍历二叉树
 * @param T
 */
void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%c", T->data);
    }
}

/**
 * 层序遍历二叉树
 * @param T
 */
void LevelOrder(BiTree T) {
    BiTNode *ptree = T;
    LinkQueue Q = InitQueue();  // 定义一个辅助队列
    // 根结点入队
    EnQueue(Q, ptree);
    while(!IsQueueEmpty(Q)) {
        printf("%c", Q.front->data->data);
        DeQueue(Q, ptree);
        if (ptree->lchild != NULL) {
            EnQueue(Q, ptree->lchild);
        }
        if (ptree->rchild != NULL) {
            EnQueue(Q, ptree->rchild);
        }
    }
}

/**
 * 读取字符串abcdefghij，然后层次建树建立一颗二叉树，然后中序遍历输出 hdibjeafcg，后序遍历输出 hidjebfgca，层序遍历输出abcdefghij
 * @return
 */
int main() {
    // 定义一棵二叉树
    BiTree T = NULL;
    // 定义一个辅助队列（不带头结点）
    LinkQueue Q = InitQueue();

    // 层序建树
    ElemType_Tree e;
    while (scanf("%c", &e) != EOF) {
        if (e == '\n') {
            break;
        }
        BiTNode *tnew = (BiTNode*) calloc(1, sizeof (BiTNode));
        tnew->data = e;
        if (T == NULL) {
            // 第一个结点入队
            EnQueue(Q, tnew);
            // 第一个结点入树
            T = tnew;
        } else {
            // 结点入队
            EnQueue(Q, tnew);
            // 结点入树
            if (Q.front->data->lchild == NULL) {
                Q.front->data->lchild = tnew;
            } else {
                Q.front->data->rchild = tnew;
                DeQueue(Q, tnew);
            }
        }
    }

    // 打印二叉树
    InOrder(T);
    printf("\n");
    PostOrder(T);
    printf("\n");
    LevelOrder(T);
    printf("\n");

    return 0;
}